package solutions.leetcode.normal

import solutions.lib.TreeNode

/**
 * @author lzd
 * <a href="https://leetcode.cn/problems/maximum-binary-tree-ii/">998. 最大二叉树 II</>
 */
class Solution998 {
    fun insertIntoMaxTree(root: TreeNode?, value: Int): TreeNode? {
        if ((root?.`val` ?: 0) <= value) {
            return TreeNode(value, root, null)
        }
        var nowNode = root
        while (nowNode != null) {
            val rightVal = (nowNode.right?.`val` ?: 0)
            if (value < rightVal) {
                nowNode = nowNode.right
            } else {
                val node = TreeNode(value, nowNode.right, null)
                nowNode.right = node
                break
            }
        }
        return root
    }
}